package com.likeycy.my.sort.cmp;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName: ShellSort
 * @Description: 希尔排序：可以看做是插入排序的改进版
 * @Author: sodagreen
 * @Date: 2021/4/3 9:10
 * @Version: 1.0
 */
public class ShellSort<T extends Comparable<T>> extends Sort<T> {

    @Override
    protected void sort() {
        List<Integer> stepSequence = sedgewickStepSequence();
        for (Integer step : stepSequence) {
            sort(step);
        }
    }

    /**
     * 分成 step（步长）列进行排序。
     * 元素在数组中的索引位置公式为：col + row * step
     *
     * @param step
     */
    private void sort(int step) {
        // col：第几列，column的简称
        for (int col = 0; col < step; col++) {
            // 对第col列进行排序
            // 对 [0, array.length) 范围的元素进行插入排序
            // col、col+step、col+2*step、col+3*step
            for (int begin = col + step; begin < array.length; begin += step) {
                int cur = begin;
                while (cur > col && cmp(cur, cur - step) < 0) {
                    swap(cur, cur - step);
                    cur -= step;
                }
            }
        }
    }

    /**
     * 生成希尔排序步长</p>
     * 希尔本人体用的步长最坏时间复杂度会到达 O(n^2)。所以在下一个方法改进为最佳生成步长方法 </p>
     * @return
     */
    private List<Integer> shellStepSequence() {
        List<Integer> stepSequence = new ArrayList<>();
        int step = array.length;
        while ((step = step >> 1) > 0) {
            stepSequence.add(step);
        }
        return stepSequence;
    }

    private List<Integer> sedgewickStepSequence() {
        List<Integer> stepSequence = new ArrayList<>();
        int k = 0, step = 0;
        while (true) {
            // 偶数步长算法
            if (k % 2 == 0) {
                int pow = (int) Math.pow(2, k-1);
                step = 1 + 9 * (pow * pow -pow);
            } else {
                // 奇数步长算法
                int pow1 = (int) Math.pow(2, (k -1) >> 1);
                int pow2 = (int) Math.pow(2, (k +1) >> 1);
                step = 1 + 8 * pow1 * pow2 - 6 * pow2;
            }
            if (step >= array.length) {
                break;
            }
            stepSequence.add(0, step);
            k++;
        }
        return stepSequence;
    }
}
